package org.mmtk.plan.scale.colors;

import org.mmtk.plan.scale.ScaleTrace;
import org.mmtk.plan.scale.utils.MersenneTwisterFast;
import org.mmtk.plan.scale.utils.ScaleLogger;
import org.mmtk.policy.Space;
import org.mmtk.utility.Log;
import org.mmtk.utility.options.Options;
import org.mmtk.vm.VM;
import org.vmmagic.pragma.Inline;
import org.vmmagic.pragma.Uninterruptible;
import org.vmmagic.unboxed.Address;
import org.vmmagic.unboxed.ObjectReference;

@Uninterruptible
public final class CMHelperTraceLocal extends SColorsTraceLocal {
	/****************************************************************************
	 * Instance fields
	 */
	private Color color;
	private MersenneTwisterFast random;

	/**
	 * Constructor
	 */
	public CMHelperTraceLocal(String name, ScaleTrace trace) {
		super(name, SColors.SCAN_HELP, trace);
		long seed = ObjectReference.fromObject(trace).toAddress().toLong();
		if (Options.scaleDebug.getValue() > 3) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("CMHelperTraceLocal, random generetor seed=");
			Log.writeln(seed);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		random = new MersenneTwisterFast(seed);
	}

	@Override
	public void prepare() {
		super.prepare();
	}

	/**
	 * This method is the core method during the trace of the object graph. The
	 * role of this method is to:
	 * 
	 * 1. Ensure the traced object is not collected. 2. If this is the first
	 * visit to the object enqueue it to be scanned. 3. Return the forwarded
	 * reference to the object.
	 * 
	 * In this instance, we refer objects in the mark-sweep space to the msSpace
	 * for tracing, and defer to the superclass for all others.
	 * 
	 * @param object
	 *            The object to be traced.
	 * @return The new reference to the same object instance.
	 */
	@Inline
	@Override
	public ObjectReference traceObject(ObjectReference object) {
		//null
		if (object.isNull()) {
			return object;
		}

		//colors table
		if (object == Color.tableRef) {
			Log.prependThreadId();
			Log.write("CMHelperTraceLocal.traceObject !!! color table, object=");
			Log.writeln(object);
			Log.flush();
		}

		//invalid
		if (!VM.objectModel.validRef(object)) {
			if (Options.scaleDebug.getValue() > 3) {
				ScaleLogger.acquireLogLock();
				Log.prependThreadId();
				Log.write("CMHelperTraceLocal.traceObject: invalid object=");
				Log.flush();
				VM.objectModel.dumpObject(object);
				Log.flush();
				ScaleLogger.releaseLogLock();
			}
			invalidTraced++;
			return object;
		}
		
		if (Options.scaleDebug.getValue() > 5) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("CMHelperTraceLocal.traceObject, object=");
			Log.flush();
			VM.objectModel.dumpObject(object);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}

		//other space
		if (!Space.isInSpace(SColors.SCALE_MS_SPACE, object)) {
			if (Options.scaleDebug.getValue() > 3) {
				ScaleLogger.acquireLogLock();
				Log.prependThreadId();
				Log.write("CMHelperTraceLocal.traceObject OSO, color=");
				Log.write(color.getIndex());
				Log.write(", object=");
				Log.flush();
				VM.objectModel.dumpObject(object);
				Log.flush();
				ScaleLogger.releaseLogLock();
			}
			color.addOtherSpace(object);
			return super.traceObject(object);
		}

		int regColor = SColors.scaleSpace.getColor(object);
		ObjectReference objColorMarkRef = VM.objectModel.getKathy(object);
		int objColorMark;
		if (objColorMarkRef == ObjectReference.nullReference()) {
			objColorMark = 0;
		} else {
			objColorMark = objColorMarkRef.toAddress().toInt();
		}
		if (Options.scaleDebug.getValue() > 5) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("CMHelperTraceLocal.traceObject color=");
			Log.write(color.getIndex());
			Log.write(", regColor=");
			Log.write(regColor);
			Log.write(", objColorMark=");
			Log.write(objColorMark);			
			Log.write(", object=");
			Log.flush();
			VM.objectModel.dumpObject(object);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}

		// traced by regular tracer - do nothing
		if (SColors.scaleSpace.isLive(object)) {	
			return object;
		}
		
		if (objColorMark == color.getIndex()) {
			// traced by this helper? - do nothing
			return object;
		}

		if (objColorMark != 0) {
			// traced by other helper - mark dependent helper
			// TODO do this atomically to prevent unneeded dependencies among
			// colors
			Color objColor = Color.getColor(objColorMark);
			if (objColor == null) {
				//sanity
				ScaleLogger.acquireLogLock();
				Log.writeln("\t !!! traceObject, other helper is null");
				Log.flush();
				VM.objectModel.dumpObject(object);
				ScaleLogger.releaseLogLock();
			} else {
				if (Options.scaleDebug.getValue() > 5) {
					ScaleLogger.acquireLogLock();
					Log.prependThreadId();
					Log.write("\ttraceObject, adding depending color from ");
					Log.write(color.getIndex());
					Log.write(" to ");
					Log.writeln(objColorMark);
					Log.flush();
					VM.objectModel.dumpObject(object);
					ScaleLogger.releaseLogLock();
				}
				color.addDependentColor(objColorMark);
			}
			return object;
		}

		if (atomicallyColor(object)) {
			processNode(object);
			color.addColored(regColor);
		}

		return object;
	}

	protected void giveUpRoots() {
		this.rootLocations.flushLocal();
	}

	public void helperTrace(Color color) {
		this.color = color;
		if (Options.scaleDebug.getValue() > 3) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("helperTrace - enter, colorMark=");
			Log.writeln(color.getColorMark());
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		ObjectReference root = obtainRoot();
		if(root != null) {
			color.setRoot(root);
			color.addColored(SColors.scaleSpace.getColor(root));
			this.processNode(root);
			completeHelperTraceBFS();
			color.setDone();
		}
		if (Options.scaleDebug.getValue() > 3) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("helperTrace - exit ");
			color.dump();
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
	}

	/**
	 * Finishing processing all GC work. This method iterates until all work
	 * queues are empty.
	 */
	@Inline
	public void completeHelperTraceDFS() {
		long valuesPopped = 0;
		if (!rootLocations.isEmpty()) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.writeln("\tcompleteHelperTraceDFS - !!! need to process roots - strange");
			ScaleLogger.releaseLogLock();
			processRoots();
		}

		assertMutatorRemsetsFlushed();
		do {
			while (!values.isEmpty()) {
				if (color.isDone()) {
					// TODO - leave this color, get another one, evacuate
					// remaining objects
					color.saveObjectsFront(values);
					if (Options.scaleDebug.getValue() > 5) {
						ScaleLogger.acquireLogLock();
						Log.prependThreadId();
						Log.writeln("\tcompleteHelperTraceDFS - color is exausted, stack is saved");
						Log.flush();
						ScaleLogger.releaseLogLock();
					}
					break;
				}
				ObjectReference v = values.pop();
				if (Options.scaleDebug.getValue() > 5) {
					ScaleLogger.acquireLogLock();
					Log.prependThreadId();
					Log.write("\tcompleteHelperTraceDFS - popped v=");
					Log.writeln(v);
					Log.flush();
					ScaleLogger.releaseLogLock();
				}
				valuesPopped++;
				scanObject(v);
			}
			processRememberedSets();
		} while (!values.isEmpty());

		if (Options.scaleDebug.getValue() > 3) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("\tcompleteHelperTraceDFS - exit, valuesPopped=");
			Log.writeln(valuesPopped);
			ScaleLogger.releaseLogLock();
		}
		assertMutatorRemsetsFlushed();
	}

	/**
	 * Finishing processing all GC work. This method iterates until all work
	 * queues are empty.
	 */
	@Inline
	public void completeHelperTraceBFS() {
		long valuesPopped = 0;
		if (!rootLocations.isEmpty()) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.writeln("\tcompleteHelperTraceBFS - !!! need to process roots - strange");
			ScaleLogger.releaseLogLock();
			processRoots();
		}

		assertMutatorRemsetsFlushed();
		do {
			while (!values.isEmpty()) {
				if (color.isDone()) {
					// TODO - leave this color, get another one, evacuate
					// remaining objects
					color.saveObjectsFront(values);
					if (Options.scaleDebug.getValue() > 5) {
						ScaleLogger.acquireLogLock();
						Log.prependThreadId();
						Log.writeln("\tcompleteHelperTraceBFS - color is exausted, stack is saved");
						Log.flush();
						ScaleLogger.releaseLogLock();
					}
					break;
				}
				copyValues();
				// printClosureCounts("completeMetrixTrace -  after copying values");
				ObjectReference v;
				do {
					while (!toEmpty.isEmpty()) {
						v = toEmpty.pop();
						if (Options.scaleDebug.getValue() > 5) {
							ScaleLogger.acquireLogLock();
							Log.write("completeHelperTraceBFS - popped object ");
							Log.write(currentClosureCounts.getMsPopped());
							Log.write(" ");
							Log.write(currentClosureCounts.getMsPushed());
							Log.write(" ");
							Log.write(currentClosureCounts.getDepth());
							Log.write(", space=");	
							Log.write(Space.getSpaceForObject(v).getName());
							Log.write(" ");	
							Log.flush();
							VM.objectModel.dumpObject(v);
							Log.flush();
							ScaleLogger.releaseLogLock();
						}
						valuesPopped++;
						scanObject(v);
					}
					processRememberedSets();
				} while (!toEmpty.isEmpty());
				super.assertMutatorRemsetsFlushed();
				// printClosureCounts("completeMetrixTrace - after processing values");
			}
			processRememberedSets();
		} while (!values.isEmpty());

		if (Options.scaleDebug.getValue() > 3) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("\tcompleteHelperTraceBFS - exit, valuesPopped=");
			Log.writeln(valuesPopped);
			ScaleLogger.releaseLogLock();
		}
		assertMutatorRemsetsFlushed();
	}

	private ObjectReference obtainRoot() {
		ObjectReference result = null;

		while (!SColors.tracersDone()) {
			int numRegions = SColors.scaleSpace.getNumRegions();
			int regionNumber = (int) random.nextLong(numRegions);
			long regionSize = SColors.scaleSpace.getRegionSize(regionNumber);
			int randomInt = (int) random.nextLong(regionSize);
			randomInt = randomInt - randomInt % 4;
			Address randomAddress = SColors.scaleSpace.getRegionStart(
					regionNumber).plus(randomInt);
			ObjectReference randomObject = SColors.scaleSpace
					.findRootCandidate(randomAddress, color.getIndex()%11+2);
			if (Options.scaleDebug.getValue() > 3) {
				ScaleLogger.acquireLogLock();
				Log.prependThreadId();
				Log.write("obtainRoot, numRegions=");
				Log.write(numRegions);
				Log.write(", regionNumber=");
				Log.write(regionNumber);
				Log.write(", regionSize=");
				Log.write(regionSize);
				Log.write(", randomInt=");
				Log.write(randomInt);
				Log.write(", randomAddress=");
				Log.write(randomAddress);
				Log.write(", randomObject=");
				if (randomObject == ObjectReference.nullReference()) {
					Log.writeln("null");
				} else {
					Log.flush();
					VM.objectModel.dumpObject(randomObject);
				}
				Log.flush();
				ScaleLogger.releaseLogLock();
			}

			if (randomObject != ObjectReference.nullReference()
					&& atomicallyColor(randomObject)) {
				if (Options.scaleDebug.getValue() > 3) {
					ScaleLogger.acquireLogLock();
					Log.prependThreadId();
					Log.write("obtainRoot, root=");
					Log.flush();
					VM.objectModel.dumpObject(randomObject);
					Log.flush();
					ScaleLogger.releaseLogLock();
				}
				result = randomObject;
				break;
			}
		}

		return result;
	}

	private boolean atomicallyColor(ObjectReference object) {
		boolean result = false;

		Helper.acquireHelpersLock();
		ObjectReference objColorMarkRef = VM.objectModel.getKathy(object);
		int objColorMark;
		if (objColorMarkRef == ObjectReference.nullReference()) {
			objColorMark = 0;
		} else {
			objColorMark = objColorMarkRef.toAddress().toInt();
		}

		if (objColorMark == 0) {
			VM.objectModel.setKathy(object, color.getColorMark());
			// check the object is not marked in a meanwhile
			if (!SColors.scaleSpace.isLive(object)) {
				result = true;
				if (Options.scaleDebug.getValue() > 5) {
					ScaleLogger.acquireLogLock();
					Log.prependThreadId();
					Log.write("atomicallyColor, object=");
					Log.flush();
					VM.objectModel.dumpObject(object);
					Log.flush();
					ScaleLogger.releaseLogLock();
				}
			} else {
				// TODO - check if this is ok
				VM.objectModel.setKathy(object, ObjectReference.nullReference());
				if (Options.scaleDebug.getValue() > 5) {
					ScaleLogger.acquireLogLock();
					Log.prependThreadId();
					Log.write("atomicallyColor, tracers marked the candidate root");
					Log.flush();
					VM.objectModel.dumpObject(object);
					Log.flush();
					ScaleLogger.releaseLogLock();
				}
			}
		} else {
			if (Options.scaleDebug.getValue() > 5) {
				ScaleLogger.acquireLogLock();
				Log.prependThreadId();
				Log.write("atomicallyColor, someone else colored the candidate root, adding depending color from ");
				Log.write(color.getColorMark());
				Log.write(" to ");
				Log.writeln(objColorMark);
				Log.flush();
				VM.objectModel.dumpObject(object);
				Log.flush();
				ScaleLogger.releaseLogLock();
			}
			color.addDependentColor(objColorMark);
		}
		Helper.releaseHelpersLock();
		return result;
	}
}
